//--Built in system
#include "StdAfx.h"
#include "Graph.h"
//--
//--Using library read file
#include "iostream"
#include "fstream"
//--
using namespace std;
//--Function MatrixInit
void Graph::MatrixInit(int N,vector< vector<int> > &Array2D)
{
	Array2D.resize(N);
	for (int i = 0;i < Array2D.size(); i++)
	{
		Array2D[i].resize(N);
	}
}
void Graph::MatrixInit(int N,vector<int> &Array)
{
	Array.resize(N);
	for (int i = 0; i < Array.size(); i++)
	{
		Array[i] = -1;
	}
}
//--
//--Function GetData
void Graph::GetData(char *filename)
{	
	ifstream fin;
	fin.open(filename);
	fin >> N;
	MatrixInit(N,L);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			fin >> L[i][j];
		}
	}
	fin >> s;
	fin >> t;
	fin.close();
}
//--
void Graph::WriteData(char *filename)
{
	//--Out screen weight
	ofstream fin;
	fin.open(filename);
	printf("%d\n",D[t]);
	fin << (D[t]) << "\n";
	//--
	//--Out screen shortest way
	vector<int> temp;
	while(Labels[t] != -1)
	{
		temp.push_back(t);
		t = Labels[t];
	}
	temp.push_back(s);
	for (int i = temp.size()-1; i > -1; i--)
	{
		printf("%d ",temp[i]);
		fin << (temp[i]) <<" ";
	}
	fin << "\n";
	fin.close();
	printf("\n");
	//
}
//--
//--Function Check Peak t
int Graph::CheckPeak_t(int t, vector< vector<int> > V)
{
	int checked = 0;
	for (int i = 0; i < N; i++)
	{
		if(V[0][i] == t && V[1][t] != 0)
		{
			checked = 1;
			return checked;
		}
	}
	return checked;
}
//--
//--Function Choose Peak v
int Graph::ChoosePeak_v(vector<vector <int> >V)
{
	int peak = -1;
	int minimum = -1;
	for (int i = 0; i < N; i++)
	{
		if ((V[1][i] != 0) && ((minimum == -1 && (D[i] > minimum)) || (D[i] < minimum)))
		{
			minimum = D[i];
			peak = i;
		}
	}
	return peak;
}
//--
//--Function Dijkstra
void Graph::Dijkstra()
{
	//--Step 1 :
	//--1.1.V = X
	vector<vector <int> >V(2, vector <int>(N,0));
	for (int i = 0; i < N; i++)
	{
		V[0][i] = i;
		V[1][i] = 1;
	}
	//--1.2.D[s] = 0
	MatrixInit(N,D);
	D[s] = 0;
	//--1.3.D[k] = MAXIMUM, with all k in X \ {s}
	for (int i = 0; i < N; i++)
	{
		if (D[i] != 0)
		{
			D[i] = MAXIMUM;
		}
	}
	//--1.4.Labels[k] = -1, with all k in X
	MatrixInit(N,Labels);
	//--
	//--Step 2 :
	//--2.1.While t in V
	while (CheckPeak_t(t,V) == 1)
	{
		//--2.2.Choose v in V with D[v] is minimum
		int v = ChoosePeak_v(V);
		if (v == -1)
		{
			break;
		}
		//--2.3.V = V \ {v}
		V[1][v] = 0;
		//--2.4.With all peaks k in V anh connected from v to k
		for (int k = 0; k < N; k++)
		{
			if(L[v][k] > 0)
			{
				//--2.5.If D[k] > D[v] + Lvk
				if (D[k] > (D[v] + L[v][k]))
				{
					//--2.6.D[k] = D[v] + L[v][k]
					D[k] = D[v] + L[v][k];
					//--2.7.Labels[k] = v
					Labels[k] = v;
				}
			}
		}
	}	
	//--
}
//--